package com.south.base.test.arithmetic;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 杨辉三角
 *
 * @author Administrator
 * @date 2020/6/23 10:49
 */
public class PascalTriangle {
    public static List<List<Integer>> BASE = new ArrayList<>(Arrays.asList(Arrays.asList(1), Arrays.asList(1, 1), Arrays.asList(1, 2, 1), Arrays.asList(1, 3, 3, 1), Arrays.asList(1, 4, 6, 4, 1)));

    @Test
    public void test() {
        Assert.assertEquals("[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1]]", generate(6).toString());
        Assert.assertEquals("[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]", generate(5).toString());
        Assert.assertEquals("[1, 4, 6, 4, 1]", getRow(4).toString());
    }

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        if (BASE.size() < numRows) {
            int nums = numRows - BASE.size();
            for (int i = 0; i < nums; i++) {
                List<Integer> row = new ArrayList<>();
                row.add(1);
                List<Integer> pre = BASE.get(BASE.size() - 1);
                for (int j = 1; j < pre.size(); j++) {
                    row.add(pre.get(j) + pre.get(j - 1));
                }
                row.add(1);
                BASE.add(row);
            }
        }
        for (int i = 0; i < numRows; i++) {
            res.add(BASE.get(i));
        }
        return res;
    }

    public List<Integer> getRow(int rowIndex) {
        if (BASE.size() < rowIndex + 1) {
            generate(rowIndex + 1);
        }
        return BASE.get(rowIndex);
    }
}
